'''
basic -27  2n皇后问题

问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。
    现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，
    任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，
    如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
　　输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
提交代码
'''

"""
Author: CharlesWYQ Time: 2021/3/5 17:05
Name: BASIC-27 VIP试题 2n皇后问题(*)
N皇后问题是指在一个N*N的棋盘上放置N个皇后，使得它们互相之间不能攻击到对方（即不能在同一行、同一列或同一对角线上）。
这段代码使用了深度优先搜索的方法来求解N皇后问题。



# 首先，导入collections模块中的defaultdict类，用于创建一个默认值为布尔值的字典。
from collections import defaultdict

# 然后，通过输入函数获取一个整数N，表示棋盘的大小。
n = int(input())

# 接下来，通过循环获取输入的棋盘状态，并将其存储在二维列表board中。
board = []
for i in range(n):
    board.append(input().split())
# col1：记录第一列上哪些格子被黑方占据。
# dia11和dia21：分别记录两条对角线上哪些格子被黑方占据。
# col2：记录第二列上哪些格子被黑方占据。
# dia12和dia22：分别记录两条对角线上哪些格子被黑方占据。
col1 = defaultdict(bool)
dia11 = defaultdict(bool)
dia21 = defaultdict(bool)
col2 = defaultdict(bool)
dia12 = defaultdict(bool)
dia22 = defaultdict(bool)

# 接着，定义了一些辅助函数和全局变量。
# 全局变量count用于记录解的个数。
# # 辅助函数dfs2用于处理第二行及之后的行，dfs1用于处理第一行。这两个函数的参数index表示当前处理的行数。
count = 0


# 参数index表示当前处理的行数。
def dfs2(index):
    global count
    # dfs2中，首先判断如果index等于N，说明所有行都已经处理完，此时将count加1表示找到了一个解，并返回。
    if index == n:
        count += 1
        return

    # 然后，通过循环遍历第index行的每个位置，
    for j in range(n):
        # 判断如果该位置没有被占据（col2[j]为False）且不在两个对角线上（dia12[index+j]和dia22[index-j]都为False），
        # 并且该位置的值为1，
        if not col2[j] and not dia12[index + j] and not dia22[index - j] and board[index][j] == "1":
            # 那么将该位置占据，并将对应的col2、dia12和dia22设置为True，
            col2[j] = True
            dia12[index + j] = True
            dia22[index - j] = True
            board[index][j] = "0"
            dfs2(index + 1)
            col2[j] = False
            dia12[index + j] = False
            dia22[index - j] = False
            board[index][j] = "1"

        # 然后递归调用dfs2函数处理下一行，处理完后将状态恢复，并继续循环尝试其他位置。

    return 0


def dfs1(index):
    # 在dfs1函数中，首先判断如果N小于等于0，则直接返回。
    if n <= 0:
        return 0
    # 然后，判断如果index等于N，说明所有行都已经处理完，此时调用dfs2函数处理第二行并返回。
    if index == n:
        dfs2(0)
        return
    # 接着，通过循环遍历第index行的每个位置，
    for j in range(n):
        # 判断如果该位置没有被占据（col1[j]为False）且不在两个对角线上（dia11[index+j]和dia21[index-j]都为False），
        # 并且该位置的值为1
        if not col1[j] and not dia11[index + j] and not dia21[index - j] \
                and board[index][j] == "1":
            #  那么将该位置占据，并将对应的col1、dia11和dia21设置为True，
            col1[j] = True
            dia11[index + j] = True
            dia21[index - j] = True
            board[index][j] = "0"
            dfs1(index + 1)
            col1[j] = False
            dia11[index + j] = False
            dia21[index - j] = False
            board[index][j] = "1"

        # 然后递归调用dfs1函数处理下一行，处理完后将状态恢复，并继续循环尝试其他位置。

    return 0


# 最后，在主函数中调用dfs1函数开始求解N皇后问题，并打印出解的个数。
dfs1(0)
print(count)
"""







# https://blog.csdn.net/weixin_50686532/article/details/121112166

# 2n皇后问题和1n皇后问题（也就是八皇后问题，一种颜色，皇后个数等于行数等于列数），几乎差不多。
# 我们这里先放置黑皇后再在此基础上放置白皇后。

n = int(input())
maze = []
vis_black = [0 for i in range(n + 1)]  # 下标表示行，列表值表示列,1表示已经有黑皇后，0表示还没有放置黑皇后
vis_white = [0 for i in range(n + 1)]  # 白皇后的
sum = 0  # 记录可行情况次数
for i in range(n):
    maze.append(input().split())


def place_black(row):  # 判断能否放置黑皇后
    if maze[row - 1][vis_black[row] - 1] == '0':  # 判断棋盘上该位置能不能放
        return False
    for i in range(1, row):
        if vis_black[i] == vis_black[row] or abs(i - row) == abs(vis_black[i] - vis_black[row]):
            # 如果现在的黑皇后位置和之前的任意一个在同一列或者同一条对角线上,则返回falze
            return False

    return True


def place_white(row):
    if maze[row - 1][vis_white[row] - 1] == '0' or vis_white[row] == vis_black[row]:  # 判断棋盘上该位置
        # 能不能放，还要判断黑皇后是否占用了这个位置
        return False
    for i in range(1, row):
        if vis_white[i] == vis_white[row] or abs(vis_white[i] - vis_white[row]) == abs(i - row):
            # 如果现在的黑皇后位置和之前的任意一个在同一列或者同一条对角线上,则返回falze
            return False

    return True


def backtrace_black(row):
    if row > n:
        backtrace_white(1)  # 黑皇后放置完后开始放置白皇后
    else:
        for i in range(1, n + 1):
            vis_black[row] = i
            if place_black(row):
                backtrace_black(row + 1)


def backtrace_white(row):
    global sum
    if row > n:
        sum += 1
        # for i in range(1,n+1):
        #     print("<黑",i,",",vis_black[i],">",end=" ")
        # print()
        # for i in range(1, n + 1):
        #     print("<白", i, ",", vis_white[i], ">", end=" ")
        # print()
    else:
        for i in range(1, n + 1):
            vis_white[row] = i
            if place_white(row):
                backtrace_white(row + 1)


backtrace_black(1)
print(sum)
